package com.zhj.leetcode;

/**
 * 力扣169 多数元素
 */
public class Test169 {
    public static void main(String[] args) {
        int[] nums = {2, 2, 2, 3, 2, 1, 1};
        int majority = getMaxMajority(nums);
        System.out.println(majority);
    }

    public static int getMaxMajority(int[] nums) {
        return getMajority(nums, 0, nums.length - 1);
    }

    private static int getMajority(int[] nums, int left, int right) {
        if (left == right) {
            return nums[left];
        }
        int mid = left + (right - left) / 2;
        int leftMajority = getMajority(nums, left, mid);
        int rightMajority = getMajority(nums, mid + 1, right);
        if (leftMajority == rightMajority) {
            return leftMajority;
        }
        int leftCount = 0;
        int rightCount = 0;
        for (int i = left; i <= right; i++) {
            if (nums[i] == leftMajority) {
                leftCount++;
            }else if (nums[i] == rightMajority) {
                rightCount++;
            }
        }
        return leftCount > rightCount ? leftMajority : rightMajority;
    }
}
